1. Field of the Invention
The present invention relates to routing packets in a communication network, and, more particularly, to scheduling routing of packets through a node of the network to guarantee levels of service between data sources and destinations.
2. Description of the Related Art
Telecommunication systems typically employ a physical hierarchical structure to integrate multiple user data channels for transmission through a medium. Transmission through the medium at one level of the hierarchy is generally at a much higher rate than the rate of each user's data at a lower level of the hierarchy. For synchronous networks, the methods employed for multiplexing may use a frame format in which data of individual user channels are inserted into predefined “slots” within a frame. Some networks have rather rigid provisioning for channel-slot allocation, while others, such as synchronous packet (cell) networks, may allocate channels within the various timeslots with greater flexibility. In addition, telecommunication systems typically employ a logical hierarchical structure. For example, packet networks may have a hierarchical structure in which smaller networks are interconnected by larger networks, and a peer structure in which equivalent networks are interconnected. However, transport of packets at one level of the hierarchy may be accomplished by dividing up packets of other levels. For example, a packet for transport through a network may be divided into smaller pieces. Each piece may then be assigned to one or more cells, each of which is itself a packet.
A user's communication path through a network comprises those nodes and links through which the user data stream traverses. Nodes may contain (packet) switching and routing equipment, multiplexing/demultiplexing, and/or other terminal equipment; and links may be those physical lines (e.g., electrical or optical) as media that connect the equipment. Interior routing protocols are employed by network nodes to determine and establish a path through the nodes of the network along which packets between a source (ingress) node and destination (egress) node pair are forwarded. Packets received by a node's router are forwarded to other nodes based on forwarding information constructed in accordance with the interior routing protocol, but may also be through routes installed with explicit route (terminal input/output port pair) provisioning. Forwarding combines the physical and logical hierarchies by specifying how packets with certain source/destination addresses received at input ports of the nodes terminal equipment are passed to particular output ports for forwarding to the intended destination. Once provisioned along a physical path through the network, a logical channel exists through which packet connections may be established at any given time. At any given node of a network through which the user communication path traverses, several processing functions may be applied to a link carrying the user's logical channel. These processing functions may be employed for switching and cross-connect (e.g., cell-relay) operations, or may be employed for re-formatting operations (e.g., convert between packet formats of different packet networks).
Routing protocols, in addition to providing connectivity, may also provide connectivity given certain provisioned service guarantees. The Multi-Protocol Label Switched (MPLS) standard, for example, allows such routing protocols in networks. The MPLS standard may be employed for networks having virtual circuits (packet flows) or label switched paths (LSPs) with provisioned service levels (also known as guaranteed quality-of-service (QoS)). Provisioned service levels may be, for example, a guaranteed minimum bandwidth for the path of a packet flow through the network, a minimum delay experienced by packets flowing through the network, or bounds on the number of lost or corrupted packets. In general, these service levels may be defined in terms of effective bandwidth.
Packet networks, such as asynchronous transfer mode (ATM) networks, commonly schedule processing and forwarding of data packets/cells received at each intermediate node. Such scheduling may be employed to reduce or prevent excessive delay experienced by packets of each user's data connection, termed a virtual circuit connection (VC-connection), as the packets are routed through the node. A relatively simple prior art method of scheduling is termed “round-robin” or “token ring” scheduling. For round-robin scheduling, cells of each logical channel are buffered in a corresponding queue, and the scheduler determines when, in relation to a system clock, the queue is eligible for service (the transfer of one or more cells from the queue to an output port). Round-robin scheduling services, in sequence, each queue (and hence, the sequence of logical channels) by examining the queue to see if it is empty, processes a non-empty queue until a specified event is detected, and then examines the next queue in the sequence. The sequence is considered “token ring” scheduling since queues are examined and, if necessary, serviced in ascending or descending order, and returns to the first queue in the sequence after the last queue in the sequence is served. As each one of the non-empty queues is served, data in the serviced queue is transferred into the slot(s) of the output frame until either of two types of events first occurs. The first type of event occurs when the currently serviced queue becomes empty. The second type of event is that a timer generates an interrupt causing the scheduler to advance to the next queue in the sequence. Timer-generated interrupts may be used to introduce “fairness” to service of queues.
Scheduling incorporating more complex methods of identifying eligible queues for service allows network providers to guarantee data transfer rates and bounds for delay through the node and the network. Network providers may then offer these rates and bounds for the VC-connections as a guaranteed service (e.g., QoS). Such algorithms for scheduling packets may achieve excellent delay and fairness properties by approximating an ideal scheduling discipline, known as a Generalized Processor Sharing (GPS) scheduling algorithm. One exemplary GPS scheduling algorithm is described in A. K. Parekh and R. G. Gallagher, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,” IEEE/ACM Trans. Networking, pp. 344–357, June 1993.
Among GPS scheduling algorithms used by a scheduler of the node, the class of packet-by-packet rate-proportional servers (P-RPS) is known in the art for near optimal delay properties. The schedulers of this class compute, for each packet/cell, or group of packets/cells, queued in the node, a “timestamp” value (the timestamp is also known as the “virtual finishing time”). The timestamp specifies when the packet(s) should be routed (transmitted) relative to packet(s) of the other VC-connections in the node. Several such P-RPS scheduling algorithms well-known in the art are: Packet-by-packet Generalized Processor Sharing (P-GPS), Virtual Clock, Frame-based Fair Queuing (FFQ), Self-Clocked Fair Queuing (SCFQ), and Starting-Potential Fair Queuing (SPFQ). These algorithms differ in the specific measure or function used as the system potential (predefined service time reference that may be calculated on an on-going basis) to compute the timestamps.
In addition to delay properties, another measure of scheduling algorithm performance is the “fairness” of the scheduling discipline. Fairness is generally used to characterize the priority or distribution of delay that the scheduler assigns to servicing packet(s) of each connection in the queues when the node is backlogged (i.e., when the queues are not empty while servicing or completing service of a connection). Two measures of fairness are commonly employed in the art. The first fairness measure is the service fairness index that measures the distance (as mathematically defined, such as the Euclidean distance) of the particular scheduling discipline from the ideal fairness of GPS in distributing service to VC-connections that are simultaneously backlogged. The second fairness measure is the worst-case fairness index (WFI) that measures the maximum amount of time that packets of a backlogged VC-connection may have to wait between two consecutive services (e.g., processing and routing of two separately received groups of packets).
However, demand for bandwidth, higher speed link capabilities, and requirements of QoS provisioning force terminal equipment that provides packet switching through a node to operate at increasingly higher rates. A current goal of switch designers is to expand switch capacity (switching fabric) to operate at 10, or even 100, Tbps (terabits per second) while allowing scaling of the switch fabric from 10's to 1000's of ports. A challenge of such design is to maintain the QoS requirements for network protocols, such as provided in IP, ATM, and MPLS networks, when servicing traffic at Tbps rates. Scheduler design, both in its structure and algorithms employed to allocate service, directly effects whether the switch can maintain these QoS requirements.